18. Quiz: N-Grams
N-Grams
An N-Gram is an ordered sequence of words. For example:
In the following series of quizes, you will work with 2-grams, or bigrams, as they are more commonly called.
The objective is to create a function that calculates the probability that a particular sentence
could occur in a corpus of text, based on the probabilities of its component bigrams. We'll do this in stages though:
- Quiz 1 - Extract tokens and bigrams from a sentence
- Quiz 2 - Calculate probabilities for bigrams
- Quiz 3 - Calculate the log probability of a given sentence based on a corpus of text using bigrams
Assumptions and terminology
We will assume that text data is in the form of sentences with no punctuation. If a sentence is in a single line, we will add add a token for
start of sentence: <s> and end of sentence: </s>. For example, if the sentence is "I love language models." it will appear in code as:
'I love language models'The tokens for this sentence are represented as an ordered list of the lower case words plus the start and end sentence tags:
tokens = ['<s>', 'i', 'love', 'language', 'models', '</s>']The bigrams for this sentence are represented as a list of lower case ordered pairs of tokens:
bigrams = [('<s>', 'i'), ('i', 'love'), ('love', 'language'), ('language', 'models'), ('models', '</s>')]Quiz 1 Instructions
In the quiz below, write a function that returns a list of tokens and a list of bigrams for a given sentence. You will need to first break a sentence into words in a list, then add a <s> and <s/> token to the
start and end of the list to represent the start and end of the sentence.
Your final lists should be in the format shown above and called out in the function doc string.
Start Quiz:
Probabilities and Likelihoods with Bigrams
Recall from a previous video that the probability of a series of words
can be calculated from the chained probabilities of its history:
The probabilities of sequence occurrences in a large textual corpus can be calculated this
way and used as a language model to add grammar and contectual knowledge to a speech
recognition system. However, there is a prohibitively large number of calculations for all the
possible sequences of varying length in a large textual corpus.
To address this problem, we use the Markov Assumption to approximate
a sequence probability with a shorter sequence:
In the bigram case, the equation reduces to a series of bigram probabilities multiplied together to find the approximate probability for a sentence. A concrete example:
\qquad \qquad P("I\: Iove\: language\: models") \approx
\qquad \qquad \qquad \qquad P("love"|"I")P("language"|"love")P("models"|"language")
We can calculate the probabilities by using counts of the bigramsand individual tokens. The counts are represented below with the c() operator:
In Python, the Counter method is useful for this task
from collections import Counter
# Sentence: "I am as I am"
tokens = ['<s>', 'i', 'am', 'as', 'i', 'am', '</s>']
token_counts = Counter(tokens)
print(token_counts)
# output:
# Counter({'</s>': 1, '<s>': 1, 'am': 2, 'as': 1, 'i': 2})Quiz 2 Instructions
In the quiz below, write a function that returns a probability dictionary when given a lists of tokens and bigrams.
Start Quiz:
Smoothing and logs
There are still a couple of problems to sort out before we use the bigram probability dictionary to calculate the probabilities of new sentences:
1. Some possible combinations may not exist in our probability dictionary but are still possible. We don't want to multiply in a probability of 0 just because our original corpus was deficient. This is solved through "smoothing". There are a number of methods for this, but a simple one is the Laplace smoothing with the "add-one" estimate where V is the size of the vocabulary for the corpus, i.e. the number of unique tokens:
2. Repeated multiplications of small probabilities can cause underflow problems in computers when
the values become to small. To solve this, we will calculate all probabilities in log space:
\qquad \qquad \qquad log(p_1\times p_2\times p_3\times p_4) = \log p_1 + \log p_2 + \log p_3 + \log p_4
Quiz 3 Instructions
In the following quiz, a utility named utils.bigram_add1_logs has been added for you with Laplace smoothing in the log space. Write a function that calculates the log probability for a given sentence, using this log probability dictionary. If all goes well, you should observe that more likely sentences yield higher values for the log probabilities.
Start Quiz: